package leetcode.每日一题;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author :songyaozhang
 * @date :Created 2021/8/17 19:34
 * @description :https://leetcode-cn.com/problems/permutations/
 */
public class 全排列 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.permute(new int[]{1, 2, 3}));

    }

    class Solution {
        private List<List<Integer>> ans = new ArrayList<>();
        public List<List<Integer>> permute(int[] nums) {
            List<Integer> list = new ArrayList<>();
            for (int num : nums) {
                list.add(num);
            }
            backtrack(nums.length, list, 0);
            return ans;
        }

        private void backtrack(int n, List<Integer> list, int first) {
            if (n == first) {
                ans.add(new ArrayList<>(list));
                return;
            }
            for (int i = first; i < n; i++) {
                Collections.swap(list, first, i);
                backtrack(n, list, first + 1);
                Collections.swap(list, first, i);
            }
        }
    }
}
